# Problem 14
#
# The following iterative sequence is defined for the set of positive integers:
#
#     n -> n/2 (n is even)
#     n -> 3n + 1 (n is odd)
#
# Using the rule above and starting with 13, we generate the following sequence:
#
#     13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
#
# It can be seen that this sequence (starting at 13 and finishing at 1) contains 
# 10 terms. Although it has not been proved yet (Collatz Problem), it is thought
# that all starting numbers finish at 1.
#
# Which starting number, under one million, produces the longest chain?
#
# NOTE: Once the chain starts the terms are allowed to go above one million.

def iter_seq(n):
    while n > 1:
        if n & 1 != 0:
            n = (3*n) + 1
        else:
            n = n/2
        yield n


def count_steps(n):
    f = iter_seq(n)
    arr = []
    arr.append(n)
    while True:
        try:
            #print f.next()
            arr.append(f.next())
        except StopIteration:
            break
    return len(arr)

MAX_N = -1
MAX_STEPS = 0

for n in range(999999,1,-1):
    s = count_steps(n)
    #print "%d: %d steps" % (n, s)
    if s > MAX_STEPS:
        MAX_STEPS = s
        MAX_N = n

print "-> MAX n: %d, steps: %d" % (MAX_N, MAX_STEPS)
